package _08_DFS_BFS;

import java.util.LinkedList;
import java.util.Queue;

public class _994_腐烂的橘子 {

    public static void main(String[] args) {
        _994_腐烂的橘子 v = new _994_腐烂的橘子();
        int[][] ins = new int[][]{
                {2, 1, 1},
                {1, 1, 1},
                {0, 1, 2}
        };

        System.out.println(v.orangesRotting(ins));
    }

    private int rows;

    private int cols;

    private int[][] vector = new int[][]{
            {1, 0},
            {-1, 0},
            {0, 1},
            {0, -1}
    };

    public int orangesRotting(int[][] grid) {
        rows = grid.length;
        cols = grid[0].length;
        // 统计当前表格中有多少个新鲜的橘子
        int count = 0;
        int level = 0;
        // 收集到所有已经腐烂的橘子
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 1) {
                    count++;
                } else if (grid[i][j] == 2) {
                    queue.offer(new int[]{i ,j, 0});
                }
            }
        }
        while (!queue.isEmpty()) {
            int[] info = queue.poll();
            level = info[2];
            int addLevel = info[2] + 1;
            for (int[] ints : vector) {
                int row = info[0] + ints[0];
                int col = info[1] + ints[1];
                if (row >= 0 && row < rows && col >= 0 && col < cols && grid[row][col] == 1) {
                    // 新鲜橘子，变腐烂
                    grid[row][col] = 2;
                    // 入队
                    count--;
                    queue.offer(new int[]{row, col, addLevel});
                }
            }
        }
        return count == 0 ? level : -1;
    }

}
